0386. 字典序排数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

给你一个整数 n，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

---

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：

输入：n = 2
输出：[1,2]

---

提示：

• 1 <= n <= 5 * 10^4

2. 🎯 s.1 - DFS

c

void dfs(int cur, int n, int* res, int* idx) {
    if (cur > n) return;
    res[(*idx)++] = cur;
    for (int i = 0; i <= 9; i++) dfs(cur * 10 + i, n, res, idx);
}

int* lexicalOrder(int n, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * n);
    *returnSize = 0;
    for (int i = 1; i <= 9; i++) dfs(i, n, res, returnSize);
    return res;
}

js

/**
 * @param {number} n
 * @return {number[]}
 */
var lexicalOrder = function (n) {
  const res = []
  const dfs = (cur) => {
    if (cur > n) return
    res.push(cur)
    for (let i = 0; i <= 9; i++) dfs(cur * 10 + i)
  }
  for (let i = 1; i <= 9; i++) dfs(i)
  return res
}

py

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        res = []
        def dfs(cur):
            if cur > n:
                return
            res.append(cur)
            for i in range(10):
                dfs(cur * 10 + i)
        for i in range(1, 10):
            dfs(i)
        return res

• 时间复杂度：$O(n)$
• 空间复杂度：$O(\log n)$，递归栈深度

算法思路：

• 字典序等价于十叉树的前序遍历
• 从 1-9 开始，每个节点向下扩展 0-9，直到超过 $n$